package com.example.swordjava;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * @Author weiwei
 * @Date 2024/3/14 17:06
 */
public class LruCache {

    private int capacity;
    //    private LinkedList<Integer> list;
    private DoublyLinkedList list;
    private HashMap<Integer, Node> map;

    public LruCache(int capacity) {
        this.capacity = capacity;
        list = new DoublyLinkedList();
        map = new HashMap<>();
    }


    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            list.remove(node);
            list.addToHead(node);
            return node.value;
        }
        return -1;
    }
//    public int get(int key){
//        if (map.containsKey(key)){
////            list.removeFirstOccurrence(key);
//            list.remove(key);
//            list.add(key);
//            return map.get(key);
//        }
//        return -1;
//    }

    public void put(int key, int value) {

        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            map.put(key, node);
            list.remove(node);
            list.addToHead(node);
        } else {
            if (map.size() == capacity) {
                Node lastNode = list.getLast();
                list.remove(lastNode);
                map.remove(lastNode.key);
            }
            Node node = new Node(key,value);
            list.addToHead(node);
            map.put(key, node);
        }

    }
//    public void put(int key,int value){
//        if (map.containsKey(key)){
//            if (list.size()==capacity){
//                int last = list.removeLast();
//                map.remove(last);
//            }
//            list.addFirst(key);
//            map.put(key,value);
//        }else {
//            map.put(key, value);
//            list.remove(key);
//            list.add(key);
//        }
//    }

    private class Node {

        Node pre;
        Node next;
        int key;
        int value;

        public Node(int key,int value) {
            this.key = key;
            this.value = value;
        }

    }

    private class DoublyLinkedList {

        Node head;
        Node tail;

        public DoublyLinkedList() {
            tail = new Node(-1, -1);
            head = new Node(-1, -1);
            tail.next = tail;
            tail.pre = head;
        }

        public void addToHead(Node node) {

            head.next.pre = node;
            node.next = head.next;
            head.next = node;
            node.pre = head;
        }

        public void remove(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
            node.pre = null;
            node.next = null;
        }

        public Node getLast() {
            if (head.next == tail) {
                return null;
            }
            return tail.pre;
        }
    }
}
